package 开始的剑指offer8月.栈与队列;

import java.util.Stack;
// https://leetcode-cn.com/problems/bao-han-minhan-shu-de-zhan-lcof/submissions/
public class 剑指Offer30包含min函数的栈0815 {
    class MinStack {

        /** initialize your data structure here. */
        private Stack<Integer> dataStack; // 数据栈
        private Stack<Integer> minStack; // 辅助栈，记录每次有元素进栈后或者出栈后，元素的最小值
        /** initialize your data structure here. */
        public MinStack() {
            // 初始化辅助栈和数据栈
            dataStack = new Stack<>();
            minStack = new Stack<>();
        }
        //Stack.Peek 与 stack.pop 的区别
        //相同点：大家都返回栈顶的值。

        //不同点：peek 不改变栈的值(不删除栈顶的值)，pop会把栈顶的值删除。
        public void push(int x) {
            // 如果记录当前数据栈中最小值的辅助栈为空，或者最小值小于 x，则将 x 设置为最小值，即进辅助栈
            if(minStack.isEmpty() || minStack.peek() > x){
                minStack.push(x);
            }else{// 如果数据栈中当前最小值 < x, 则继续将最小值设置为上次的最小值
                minStack.push(minStack.peek());
            }
            dataStack.push(x);// 数据栈，进栈
        }

        public void pop() {
            minStack.pop();// 辅助栈，栈出栈
            dataStack.pop();// 数据栈，出栈
        }

        public int top() {
            return dataStack.peek();
        }

        public int min() {
            return minStack.peek();
        }

    }

/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack obj = new MinStack();
 * obj.push(x);
 * obj.pop();
 * int param_3 = obj.top();
 * int param_4 = obj.min();
 */
}
